package com.sourcetrip.algorithm.sort.quick;

import com.sourcetrip.algorithm.abs.AbstractCustomedObjectSort;

/**
 * @author: xiaomi
 * @date: 2021/1/2
 * @description: 十大排序算法之六：快速排序（的对象比较版本） --
 * V0 是一个递归版本，但是可能会有 StackOverFlow 的隐患，所以需要再做一个 迭代版本。
 * --
 * 最好时间复杂度跟 归并排序的递归公式一样：O(nlogn)
 * --
 * 快速排序的核心要求；将数组均匀分割。否则极端情况会达到 O(n^2) 的复杂度，
 */
public class QuickCustomedSortV0<E> extends AbstractCustomedObjectSort<E> {

    //开辟一个存储临时变量的 O(1) 空间
    E pivot = null;


    @Override
    protected void sortArr(E[] objectArr) {
        quickSort(objectArr, 0, objectArr.length - 1);
    }

    //region    core methods

    /**
     * TODO:快速排序的写法：左右交换的模板！
     * @param objectArr
     * @param beginIndex
     * @param endIndex
     */
    private void quickSort(E[] objectArr, int beginIndex, int endIndex) {
        if (beginIndex == endIndex) {
            return;
        }
        int bIndex = beginIndex;
        int eIndex = endIndex;
        //int midIndex = 0;


        pivot = objectArr[beginIndex];
        //先对一个大的序列进行排序处理
        //midIndex = (beginIndex + endIndex) >> 1;
        //coverIndex = beginIndex;
        while (beginIndex < endIndex) {
            //当 begin < end 时进行循环处理

            while (beginIndex < endIndex) {
                if (compare(objectArr[endIndex], pivot) >= 0) {
                    endIndex--;
                } else {
                    objectArr[beginIndex++] = objectArr[endIndex];
                    break;
                }
            }


            while (beginIndex < endIndex) {
                if (compare(objectArr[beginIndex], pivot) < 0) {
                    beginIndex++;
                } else {
                    objectArr[endIndex--] = objectArr[beginIndex];
                    break;
                }
            }

        }
        objectArr[beginIndex] = pivot;


        //然后再进行递归完成子序列的处理
        //终于发现，原来不是 midIndex,而是考虑 pivot 落地的位置！
        if (bIndex < beginIndex) {
            quickSort(objectArr, bIndex, beginIndex);
        }

        if (beginIndex + 1 < eIndex) {
            quickSort(objectArr, beginIndex + 1, eIndex);
        }


    }

    //endregion


}
